Skip to main content

Number of 1 Bits

LeetCode 191 | Difficulty: Easy​

Easy

Problem Description​

Given a positive integer n, write a function that returns the number of set bits in its binary representation (also known as the Hamming weight).

Example 1:

Input: n = 11

Output: 3

Explanation:

The input binary string 1011 has a total of three set bits.

Example 2:

Input: n = 128

Output: 1

Explanation:

The input binary string 10000000 has a total of one set bit.

Example 3:

Input: n = 2147483645

Output: 30

Explanation:

The input binary string 1111111111111111111111111111101 has a total of thirty set bits.

Constraints:

- `1 <= n <= 2^31 - 1`

Follow up: If this function is called many times, how would you optimize it?

Topics: Divide and Conquer, Bit Manipulation

Approach​

Bit Manipulation​

Operate directly on binary representations. Key operations: AND (&), OR (|), XOR (^), NOT (~), shifts (<<, >>). XOR is especially useful: a ^ a = 0, a ^ 0 = a.

When to use

Finding unique elements, power of 2 checks, subset generation, toggling flags.

Solutions​

Complexity Analysis​

ApproachTimeSpace
Bit Manipulation$O(n) or O(1)$$O(1)$

Interview Tips​

Key Points
  • Start by clarifying edge cases: empty input, single element, all duplicates.